import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @program: LeetCode
 * @description: LeetCode : 347. 前 K 个高频元素
 * @author: WXY
 * @create: 2023-01-16 15:49
 * @Version 1.0
 **/
public class Num347_topKFrequent {
    public static class Node{
        int val;
        int count;

        public Node(int val) {
            this.val = val;
        }
    }
    public static int[] topKFrequent1(int[] nums,int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 1) + 1);
        }
        PriorityQueue<Node> heap = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o2.count - o1.count;
            }
        });
        for (int num : map.keySet()) {
            Node node = new Node(num);
            node.count = map.get(num);
            heap.add(node);
        }
        int[] ans = new int[k];
        int index = 0;
        for (int i = 0; i < k; i++) {
            Node cur = heap.poll();
            ans[index++] = cur.val;
        }
        return ans;
    }

    public static int[] topKFrequent(int[] nums,int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 1) + 1);
        }
        PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int val = entry.getKey();
            int count = entry.getValue();
            heap.add(new int[]{val, count});
        }
        int[] ans = new int[k];
        int index = 0;
        for (int i = 0; i < k; i++) {
            ans[index++] = heap.poll()[0];
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 2,2, 3, 4};
        int[] ints = topKFrequent(arr,2);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i] + " ");
        }
    }
}
